package com.leetcode.algs4.sort;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/6/14 20:45
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70, 54, 543534, 23};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int N = arr.length;
        int h = 1;
        // 将数组划分为多个分区进行排序
        while (h < N / 3) h = 3 * h + 1;
        while (h >= 1) {
            // 以h作为间隔
            for (int i = 1; i < arr.length; i++) {
                for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    swap(arr, j, j - h);
                }
            }
            h /= 3;
        }
    }

    public static void shellSort(int[] arr) {
        int N = arr.length;
        int h = 1;
        // 对原数组进行分组再排序
        while (h < N / 3) h = 3 * h + 1;
        while (h >= 1) {
            for (int i = 1; i < N; i++) {
                // 分组后，可以每隔h个字符进行比较，不需要再像一般的选择排序一样一个一个比较
                for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    swap(arr, j, j - h);
                }
            }
            h /= 3;
        }
    }


    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
